/*
	Name: 飞行路线 改造路 
	Author: There,hello 
	Date: 14-10-19 19:57
	Description: Luogu P4568 P2939 
	Algorithm: 分层最短路【模板】 
*/
#include<bits/stdc++.h>
using namespace std;
struct dd{
	int ne,to,w;
}edge[4105050];
int n,m,k,head[212020],tail,dis[212020];
bool v[212020];
#define add(x,y,z) edge[++tail].ne=head[x];edge[tail].to=y;edge[tail].w=z;head[x]=tail;
void dij(){
	priority_queue<pair<int,int> >q;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(v[x])continue;
		v[x]=1;
		for(int i=head[x];i;i=edge[i].ne){
			int diss=dis[x]+edge[i].w;
			if(dis[edge[i].to]>=diss){
				dis[edge[i].to]=diss;
				q.push(make_pair(-diss,edge[i].to));
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,x,y,z;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
		for(int j=1;j<=k;++j){
			add(x+(j-1)*n,y+j*n,0);
			add(y+(j-1)*n,x+j*n,0);
			add(y+j*n,x+j*n,z);
			add(x+j*n,y+j*n,z);			
		} 
	}
	for(int i=1;i<=n*(k+1);++i)
	dis[i]=0x7fffffff;
	dis[1]=0;
	dij();
	int ans=0x7fffffff;
	for(int i=n;i<=n*(k+1);i+=n)
	ans=min(ans,dis[i]);
	printf("%d",ans);
}